"""
给定一棵二叉树，输出所有从根节点到叶子节点的路径，路径格式为 “val->val->val”。c

"""


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def binary_tree_paths(root):
    """获取二叉树从根到叶子的所有路径（递归实现）"""
    result = []
    def dfs(node, current_path):
        if not node:
            return
        # 拼接当前节点值到路径中
        current_path += str(node.val)
        # 叶子节点：将路径加入结果集
        if not node.left and not node.right:
            result.append(current_path)
            return
        # 非叶子节点：添加路径分隔符，继续递归左右子树
        current_path += "->"
        dfs(node.left, current_path)
        dfs(node.right, current_path)
    dfs(root, "")
    return result

# 创建二叉树（复用通用函数）
def create_binary_tree(arr):
    if not arr:
        return None
    root = TreeNode(arr[0])
    queue = [root]
    index = 1
    while queue and index < len(arr):
        current = queue.pop(0)
        if arr[index] is not None:
            current.left = TreeNode(arr[index])
            queue.append(current.left)
        index += 1
        if index < len(arr) and arr[index] is not None:
            current.right = TreeNode(arr[index])
            queue.append(current.right)
        index += 1
    return root

# 测试
root1 = create_binary_tree([1, 2, 3, None, 5])
# 树结构：
#       1
#      / \
#     2   3
#      \
#       5
print(binary_tree_paths(root1))  # 输出: ['1->2->5', '1->3']
root2 = create_binary_tree([1])
print(binary_tree_paths(root2))  # 输出: ['1']